
<!DOCTYPE HTML>
<html lang="zh-hans" >
    <head>
        <meta charset="UTF-8">
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <title>72.编辑距离 · Gary的小窝</title>
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="description" content="">
        <meta name="generator" content="GitBook 3.2.3">
        <meta name="author" content="Gary">
        
        
    
    <link rel="stylesheet" href="../gitbook/style.css">

    
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-prism/prism-solarizedlight.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-search-pro/search.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-splitter/splitter.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-tbfed-pagefooter/footer.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-anchor-navigation-ex/style/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-fontsettings/website.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-theme-comscore/test.css">
                
            
        

    

    

        
    
    
    <meta name="HandheldFriendly" content="true"/>
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../gitbook/images/apple-touch-icon-precomposed-152.png">
    <link rel="shortcut icon" href="../gitbook/images/favicon.ico" type="image/x-icon">

    
    <link rel="next" href="../flutter/" />
    
    
    <link rel="prev" href="322.html" />
    

    </head>
    <body>
        
<div class="book">
    <div class="book-summary">
        
            
<div id="book-search-input" role="search">
    <input type="text" placeholder="输入并搜索" />
</div>

            
                <nav role="navigation">
                


<ul class="summary">
    
    

    

    
        
        
    
        <li class="chapter " data-level="1.1" data-path="../">
            
                <a href="../">
            
                    
                    写在前面
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="./">
            
                <a href="./">
            
                    
                    Leetcode之旅
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.2.1" data-path="1.html">
            
                <a href="1.html">
            
                    
                    1.两数之和
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.2" data-path="2.html">
            
                <a href="2.html">
            
                    
                    2.两数相加
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.3" data-path="3.html">
            
                <a href="3.html">
            
                    
                    3.无重复字符的最长子串
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.4" data-path="4.html">
            
                <a href="4.html">
            
                    
                    4.寻找两个有序数组的中位数
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.5" data-path="6.html">
            
                <a href="6.html">
            
                    
                    6.Z字形变换
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.6" data-path="9.html">
            
                <a href="9.html">
            
                    
                    9.回文数
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.7" data-path="11.html">
            
                <a href="11.html">
            
                    
                    11.盛最多水的容器
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.8" data-path="12.html">
            
                <a href="12.html">
            
                    
                    12.整数转罗马数字
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.9" data-path="13.html">
            
                <a href="13.html">
            
                    
                    13.罗马数字转整数
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.10" data-path="14.html">
            
                <a href="14.html">
            
                    
                    14.最长公共前缀
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.11" data-path="322.html">
            
                <a href="322.html">
            
                    
                    322.零钱兑换
            
                </a>
            

            
        </li>
    
        <li class="chapter active" data-level="1.2.12" data-path="72.html">
            
                <a href="72.html">
            
                    
                    72.编辑距离
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="../flutter/">
            
                <a href="../flutter/">
            
                    
                    Flutter从入门到放弃
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.3.1" data-path="../flutter/dart1.html">
            
                <a href="../flutter/dart1.html">
            
                    
                    1.Dart语言(1)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.2" data-path="../flutter/dart2.html">
            
                <a href="../flutter/dart2.html">
            
                    
                    2.Dart语言(2)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.3" data-path="../flutter/widget1.html">
            
                <a href="../flutter/widget1.html">
            
                    
                    3.Flutter初始化
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.4" data-path="../flutter/containerText.html">
            
                <a href="../flutter/containerText.html">
            
                    
                    4.Container和Text组件
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.5" data-path="../flutter/image.html">
            
                <a href="../flutter/image.html">
            
                    
                    5.Image组件
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.6" data-path="../flutter/chapter2.html">
            
                <a href="../flutter/chapter2.html">
            
                    
                    6.Flutter 技术总结
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.4" data-path="../vue/">
            
                <a href="../vue/">
            
                    
                    Vue组件精讲
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.4.1" data-path="../vue/1.html">
            
                <a href="../vue/1.html">
            
                    
                    1.provide/inject
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4.2" data-path="../vue/2.html">
            
                <a href="../vue/2.html">
            
                    
                    2.手动实现broadcast和dispatch方法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4.3" data-path="../js/form.html">
            
                <a href="../js/form.html">
            
                    
                    3.自己动手实现带校验的Form表单组件
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.5" data-path="../js/">
            
                <a href="../js/">
            
                    
                    JavaScript进阶
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.5.1" data-path="../js/proxy.html">
            
                <a href="../js/proxy.html">
            
                    
                    1.Vue.js 3.0中的响应式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5.2" data-path="../js/el.html">
            
                <a href="../js/el.html">
            
                    
                    2.Element UI 源码初探
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5.3" data-path="../js/bind.html">
            
                <a href="../js/bind.html">
            
                    
                    3.bind的模拟实现
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5.4" data-path="../js/proto.html">
            
                <a href="../js/proto.html">
            
                    
                    4.JS原型和原型链
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5.5" data-path="../js/call.html">
            
                <a href="../js/call.html">
            
                    
                    5.模拟实现call和apply
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5.6" data-path="../js/ui.html">
            
                <a href="../js/ui.html">
            
                    
                    6.使用Vue cli3搭建组件库并发布到 npm
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5.7" data-path="../js/microFE.html">
            
                <a href="../js/microFE.html">
            
                    
                    7.记一次基于qiankun的微前端的改造
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5.8" data-path="../js/git.html">
            
                <a href="../js/git.html">
            
                    
                    8.Git的使用
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.6" data-path="../vueLibrary/">
            
                <a href="../vueLibrary/">
            
                    
                    基于Vue的PC端的组件库
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.6.1" data-path="../vueLibrary/1.html">
            
                <a href="../vueLibrary/1.html">
            
                    
                    1.环境搭建
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.7" data-path="../life/">
            
                <a href="../life/">
            
                    
                    网事杂谈
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.7.1" data-path="../life/1.html">
            
                <a href="../life/1.html">
            
                    
                    1.周杰伦专辑赏析--叶惠美
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.7.2" data-path="../life/2.html">
            
                <a href="../life/2.html">
            
                    
                    2.周杰伦专辑赏析--七里香
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    

    

    <li class="divider"></li>

    <li>
        <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
            本书使用 GitBook 发布
        </a>
    </li>
</ul>


                </nav>
            
        
    </div>

    <div class="book-body">
        
            <div class="body-inner">
                
                    

<div class="book-header" role="navigation">
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href=".." >72.编辑距离</a>
    </h1>
</div>




                    <div class="page-wrapper" tabindex="-1" role="main">
                        <div class="page-inner">
                            
<div id="book-search-results">
    <div class="search-noresults">
    
                                <section class="normal markdown-section">
                                
                                <div id="anchor-navigation-ex-navbar"><i class="fa fa-navicon"></i><ul><li><span class="title-icon "></span><a href="#72-&#x7F16;&#x8F91;&#x8DDD;&#x79BB;"><b></b>72. &#x7F16;&#x8F91;&#x8DDD;&#x79BB;</a></li><li><span class="title-icon "></span><a href="#&#x4E00;-&#x9898;&#x76EE;&#x63CF;&#x8FF0;"><b></b>&#x4E00; &#x9898;&#x76EE;&#x63CF;&#x8FF0;</a></li><li><span class="title-icon "></span><a href="#&#x4E8C;-&#x89E3;&#x9898;&#x8FC7;&#x7A0B;"><b></b>&#x4E8C; &#x89E3;&#x9898;&#x8FC7;&#x7A0B;</a></li></ul></div><a href="#72-&#x7F16;&#x8F91;&#x8DDD;&#x79BB;" id="anchorNavigationExGoTop"><i class="fa fa-arrow-up"></i></a><h1 id="72-&#x7F16;&#x8F91;&#x8DDD;&#x79BB;"><a name="72-&#x7F16;&#x8F91;&#x8DDD;&#x79BB;" class="anchor-navigation-ex-anchor" href="#72-&#x7F16;&#x8F91;&#x8DDD;&#x79BB;"><i class="fa fa-link" aria-hidden="true"></i></a>72. &#x7F16;&#x8F91;&#x8DDD;&#x79BB;</h1>
<h1 id="&#x4E00;-&#x9898;&#x76EE;&#x63CF;&#x8FF0;"><a name="&#x4E00;-&#x9898;&#x76EE;&#x63CF;&#x8FF0;" class="anchor-navigation-ex-anchor" href="#&#x4E00;-&#x9898;&#x76EE;&#x63CF;&#x8FF0;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E00; &#x9898;&#x76EE;&#x63CF;&#x8FF0;</h1>
<blockquote>
<p>&#x7ED9;&#x4F60;&#x4E24;&#x4E2A;&#x5355;&#x8BCD; word1 &#x548C; word2&#xFF0C;&#x8BF7;&#x4F60;&#x8BA1;&#x7B97;&#x51FA;&#x5C06; word1 &#x8F6C;&#x6362;&#x6210; word2 &#x6240;&#x4F7F;&#x7528;&#x7684;&#x6700;&#x5C11;&#x64CD;&#x4F5C;&#x6570; &#x3002;</p>
</blockquote>
<p>&#x4F60;&#x53EF;&#x4EE5;&#x5BF9;&#x4E00;&#x4E2A;&#x5355;&#x8BCD;&#x8FDB;&#x884C;&#x5982;&#x4E0B;&#x4E09;&#x79CD;&#x64CD;&#x4F5C;&#xFF1A;</p>
<ol>
<li>&#x63D2;&#x5165;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;</li>
<li>&#x5220;&#x9664;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;</li>
<li>&#x66FF;&#x6362;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;</li>
</ol>
<p>&#x793A;&#x4F8B;1&#xFF1A;</p>
<pre class="language-"><code>&#x8F93;&#x5165;&#xFF1A;word1 = &quot;horse&quot;, word2 = &quot;ros&quot;
&#x8F93;&#x51FA;&#xFF1A;3
&#x89E3;&#x91CA;&#xFF1A;
horse -&gt; rorse (&#x5C06; &apos;h&apos; &#x66FF;&#x6362;&#x4E3A; &apos;r&apos;)
rorse -&gt; rose (&#x5220;&#x9664; &apos;r&apos;)
rose -&gt; ros (&#x5220;&#x9664; &apos;e&apos;)
</code></pre><p>&#x793A;&#x4F8B;2&#xFF1A;</p>
<pre class="language-"><code>&#x8F93;&#x5165;&#xFF1A;word1 = &quot;intention&quot;, word2 = &quot;execution&quot;
&#x8F93;&#x51FA;&#xFF1A;5
&#x89E3;&#x91CA;&#xFF1A;
intention -&gt; inention (&#x5220;&#x9664; &apos;t&apos;)
inention -&gt; enention (&#x5C06; &apos;i&apos; &#x66FF;&#x6362;&#x4E3A; &apos;e&apos;)
enention -&gt; exention (&#x5C06; &apos;n&apos; &#x66FF;&#x6362;&#x4E3A; &apos;x&apos;)
exention -&gt; exection (&#x5C06; &apos;n&apos; &#x66FF;&#x6362;&#x4E3A; &apos;c&apos;)
exection -&gt; execution (&#x63D2;&#x5165; &apos;u&apos;)
</code></pre><h1 id="&#x4E8C;-&#x89E3;&#x9898;&#x8FC7;&#x7A0B;"><a name="&#x4E8C;-&#x89E3;&#x9898;&#x8FC7;&#x7A0B;" class="anchor-navigation-ex-anchor" href="#&#x4E8C;-&#x89E3;&#x9898;&#x8FC7;&#x7A0B;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E8C; &#x89E3;&#x9898;&#x8FC7;&#x7A0B;</h1>
<p>&#x8FD9;&#x9898;&#x7B2C;&#x4E00;&#x773C;&#x770B;&#x4E0A;&#x53BB;&#x662F;&#x6BD4;&#x8F83;&#x56F0;&#x96BE;&#x7684;&#xFF0C;&#x4E3A;&#x4EC0;&#x4E48;&#x8BF4;&#x8FD9;&#x4E2A;&#x95EE;&#x9898;&#x96BE;&#x5462;&#xFF0C;&#x56E0;&#x4E3A;&#x663E;&#x800C;&#x6613;&#x89C1;&#xFF0C;&#x5B83;&#x5C31;&#x662F;&#x96BE;&#xFF0C;&#x8BA9;&#x4EBA;&#x624B;&#x8DB3;&#x65E0;&#x63AA;&#xFF0C;&#x671B;&#x800C;&#x751F;&#x754F;&#x3002;</p>
<p>&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x5206;&#x6790;&#x4E00;&#x4E0B; &#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#x4E32; s1 &#x548C;&#x5B57;&#x7B26;&#x4E32; s2&#xFF0C;&#x53EA;&#x80FD;&#x7528;&#x4E09;&#x79CD;&#x64CD;&#x4F5C;&#xFF0C;&#x8BA9;&#x6211;&#x4EEC;&#x628A; s1 &#x53D8;&#x6210; s2&#xFF0C;&#x6C42;&#x6700;&#x5C11;&#x7684;&#x64CD;&#x4F5C;&#x6570;&#x3002;&#x9700;&#x8981;&#x660E;&#x786E;&#x7684;&#x662F;&#xFF0C;&#x4E0D;&#x7BA1;&#x662F;&#x628A; s1 &#x53D8;&#x6210; s2 &#x8FD8;&#x662F;&#x53CD;&#x8FC7;&#x6765;&#xFF0C;&#x7ED3;&#x679C;&#x90FD;&#x662F;&#x4E00;&#x6837;&#x7684;&#xFF0C;&#x6240;&#x4EE5;&#x540E;&#x6587;&#x5C31;&#x4EE5; s1 &#x53D8;&#x6210; s2 &#x4E3E;&#x4F8B;&#x3002;</p>
<p>&#x89E3;&#x51B3;&#x4E24;&#x4E2A;&#x5B57;&#x7B26;&#x4E32;&#x7684;&#x52A8;&#x6001;&#x89C4;&#x5212;&#x95EE;&#x9898;&#xFF0C;&#x4E00;&#x822C;&#x90FD;&#x662F;&#x7528;&#x4E24;&#x4E2A;&#x6307;&#x9488; i,j &#x5206;&#x522B;&#x6307;&#x5411;&#x4E24;&#x4E2A;&#x5B57;&#x7B26;&#x4E32;&#x7684;&#x6700;&#x540E;&#xFF0C;&#x7136;&#x540E;&#x4E00;&#x6B65;&#x6B65;&#x5F80;&#x524D;&#x8D70;&#xFF0C;&#x7F29;&#x5C0F;&#x95EE;&#x9898;&#x7684;&#x89C4;&#x6A21;&#x3002;</p>
<p>s1 -&gt; s2 &#x53EF;&#x4EE5;&#x6709;&#x4EE5;&#x4E0B;&#x51E0;&#x79CD;&#x53EF;&#x80FD;&#xFF1A;</p>
<ol>
<li>s1[i] === s2[j]  &#x56E0;&#x4E3A;&#x8FD9;&#x4E24;&#x4E2A;&#x5B57;&#x7B26;&#x672C;&#x6765;&#x5C31;&#x76F8;&#x540C;&#xFF0C;&#x4E3A;&#x4E86;&#x4F7F;&#x7F16;&#x8F91;&#x8DDD;&#x79BB;&#x6700;&#x5C0F;&#xFF0C;&#x663E;&#x7136;&#x4E0D;&#x5E94;&#x8BE5;&#x5BF9;&#x5B83;&#x4EEC;&#x6709;&#x4EFB;&#x4F55;&#x64CD;&#x4F5C;&#xFF0C;&#x76F4;&#x63A5;&#x5F80;&#x524D;&#x79FB;&#x52A8; i,j &#x5373;&#x53EF;&#x3002;</li>
<li>&#x5982;&#x679C;&#x4E0D;&#x76F8;&#x540C; &#x90A3;&#x4E48;&#x53EF;&#x6709;&#x4E09;&#x79CD;&#x64CD;&#x4F5C; &#x589E;&#x52A0; &#x66FF;&#x6362;&#x6216;&#x8005;&#x5220;&#x9664;&#xFF0C;&#x4E09;&#x9009;&#x4E00;</li>
<li>&#x5C31;&#x662F; j &#x8D70;&#x5B8C; s2 &#x65F6;&#xFF0C;&#x5982;&#x679C; i &#x8FD8;&#x6CA1;&#x8D70;&#x5B8C; s1&#xFF0C;&#x90A3;&#x4E48;&#x53EA;&#x80FD;&#x7528;&#x5220;&#x9664;&#x64CD;&#x4F5C;&#x628A; s1 &#x7F29;&#x77ED;&#x4E3A; s2</li>
</ol>
<p>&#x6240;&#x4EE5;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x5F97;&#x51FA;&#x4E00;&#x4E0B;&#x4F2A;&#x4EE3;&#x7801;</p>
<pre class="language-"><code>if s1[i] == s2[j]:
    &#x5565;&#x90FD;&#x522B;&#x505A;&#xFF08;skip&#xFF09;
    i, j &#x540C;&#x65F6;&#x5411;&#x524D;&#x79FB;&#x52A8;
else:
    &#x4E09;&#x9009;&#x4E00;&#xFF1A;
        &#x63D2;&#x5165;&#xFF08;insert&#xFF09;
        &#x5220;&#x9664;&#xFF08;delete&#xFF09;
        &#x66FF;&#x6362;&#xFF08;replace&#xFF09;
</code></pre><p>&#x4E5F;&#x8BB8;&#x4F60;&#x4F1A;&#x95EE;&#xFF0C;&#x8FD9;&#x4E2A;&#x300C;&#x4E09;&#x9009;&#x4E00;&#x300D;&#x5230;&#x5E95;&#x8BE5;&#x600E;&#x4E48;&#x9009;&#x62E9;&#x5462;&#xFF1F;&#x5F88;&#x7B80;&#x5355;&#xFF0C;&#x5168;&#x8BD5;&#x4E00;&#x904D;&#xFF0C;&#x54EA;&#x4E2A;&#x64CD;&#x4F5C;&#x6700;&#x540E;&#x5F97;&#x5230;&#x7684;&#x7F16;&#x8F91;&#x8DDD;&#x79BB;&#x6700;&#x5C0F;&#xFF0C;&#x5C31;&#x9009;&#x8C01;&#x3002;&#x8FD9;&#x91CC;&#x9700;&#x8981;&#x9012;&#x5F52;&#x3002;</p>
<pre class="language-"><code>//&#x8FD4;&#x56DE; s1[0..i] &#x548C; s2[0..j] &#x7684;&#x6700;&#x5C0F;&#x7F16;&#x8F91;&#x8DDD;&#x79BB;
function dp(i,j){
     if(i == -1)  {
         return j + 1
     }
     if(j == -1)  {
         return i + 1
     }
    if (s1[i] == s2[j]){
        //&#x672C;&#x6765;&#x5C31;&#x76F8;&#x7B49;&#xFF0C;&#x4E0D;&#x9700;&#x8981;&#x4EFB;&#x4F55;&#x64CD;&#x4F5C;
        //s1[0..i] &#x548C; s2[0..j] &#x7684;&#x6700;&#x5C0F;&#x7F16;&#x8F91;&#x8DDD;&#x79BB;&#x7B49;&#x4E8E;
        //s1[0..i-1] &#x548C; s2[0..j-1] &#x7684;&#x6700;&#x5C0F;&#x7F16;&#x8F91;&#x8DDD;&#x79BB;
        //&#x4E5F;&#x5C31;&#x662F;&#x8BF4; dp(i, j) &#x7B49;&#x4E8E; dp(i-1, j-1)
        return dp(i - 1, j - 1)  //&#x5565;&#x90FD;&#x4E0D;&#x505A; 
    }else{
            return Math.min(
                //&#x6211;&#x76F4;&#x63A5;&#x5728; s1[i] &#x63D2;&#x5165;&#x4E00;&#x4E2A;&#x548C; s2[j] &#x4E00;&#x6837;&#x7684;&#x5B57;&#x7B26;
                //&#x90A3;&#x4E48; s2[j] &#x5C31;&#x88AB;&#x5339;&#x914D;&#x4E86;&#xFF0C;&#x524D;&#x79FB; j&#xFF0C;&#x7EE7;&#x7EED;&#x8DDF; i &#x5BF9;&#x6BD4;
                // &#x522B;&#x5FD8;&#x4E86;&#x64CD;&#x4F5C;&#x6570;&#x52A0;&#x4E00;
            dp(i, j - 1)    //&#x63D2;&#x5165;
            // &#x6211;&#x76F4;&#x63A5;&#x628A; s[i] &#x8FD9;&#x4E2A;&#x5B57;&#x7B26;&#x5220;&#x6389;
            // &#x524D;&#x79FB; i&#xFF0C;&#x7EE7;&#x7EED;&#x8DDF; j &#x5BF9;&#x6BD4;
            // &#x64CD;&#x4F5C;&#x6570;&#x52A0;&#x4E00;
            dp(i - 1, j)     // &#x5220;&#x9664;
            //&#x6211;&#x76F4;&#x63A5;&#x628A; s1[i] &#x66FF;&#x6362;&#x6210; s2[j]&#xFF0C;&#x8FD9;&#x6837;&#x5B83;&#x4FE9;&#x5C31;&#x5339;&#x914D;&#x4E86;
            // &#x540C;&#x65F6;&#x524D;&#x79FB; i&#xFF0C;j &#x7EE7;&#x7EED;&#x5BF9;&#x6BD4;
            // &#x64CD;&#x4F5C;&#x6570;&#x52A0;&#x4E00;
            dp(i - 1, j - 1) // &#x66FF;&#x6362;
        )+1
    }

      return dp((s1).length - 1, (s2).length - 1) 

}
</code></pre><p>&#x601D;&#x8DEF;&#x5DF2;&#x7ECF;&#x6709;&#x4E86; &#x63A5;&#x4E0B;&#x6765;&#x6211;&#x4EEC;&#x8981;&#x628A;&#x8FD9;&#x4E2A;&#x601D;&#x60F3;&#x53D8;&#x6210;&#x52A8;&#x6001;&#x89C4;&#x5212;&#x7684;&#x5957;&#x8DEF;&#x3002;
&#x5B9A;&#x4E49;&#x4E00;&#x4E2A;&#x4E8C;&#x7EF4;&#x6570;&#x7EC4; <code>dp[n+1][m+1]</code> &#x8868;&#x793A; &#x5728;s1[0..n] &#x548C; s2[0..m] &#x7684;&#x6700;&#x5C0F;&#x7F16;&#x8F91;&#x8DDD;&#x79BB;</p>
<p>&#x52A8;&#x6001;&#x89C4;&#x5212;&#x7684;&#x6838;&#x5FC3;&#x5C31;&#x662F;&#x72B6;&#x6001;&#x8F6C;&#x79FB;&#x65B9;&#x7A0B; &#x548C;base case &#x4E5F;&#x5C31;&#x662F;&#x6700;&#x521D;&#x503C;</p>
<p>&#x5728;&#x5B9A;&#x4E49;&#x597D;dp&#x540E;&#x6211;&#x4EEC;&#x5148;&#x5B9A;&#x4E49;&#x4E00;&#x4E0B;&#x521D;&#x59CB;&#x503C; dp[i][0] &#x548C;dp[0][j]&#x3002;
dp[i][0] &#x8868;&#x793A;s1[0..i] &#x5230;s2 &#x957F;&#x5EA6;&#x4E3A;0&#x7684;&#x8DDD;&#x79BB;&#xFF0C;&#x53EF;&#x4EE5;&#x5012;&#x63A8;&#x6210;dp[i-1][0]&#x7684;&#x8DDD;&#x79BB;&#x52A0;&#x4E00; &#xFF0C;dp[0][j] &#x7C7B;&#x4F3C;</p>
<p>&#x63A5;&#x4E0B;&#x6765;&#x8FDB;&#x884C;&#x72B6;&#x6001;&#x8F6C;&#x79FB;&#x65B9;&#x7A0B;&#x7684;&#x5B9A;&#x4E49; &#x4E5F;&#x5C31;&#x662F;&#x5FAA;&#x73AF;&#x6240;&#x6709;&#x72B6;&#x6001;&#xFF0C;&#x5224;&#x65AD;s1[i] == s2[j]&#x7684;&#x662F;&#x5426;&#x76F8;&#x7B49;  &#x6309;&#x7167;&#x4E0A;&#x9762;&#x7684;&#x601D;&#x8DEF;&#x6765;&#x5224;&#x65AD;</p>
<p>&#x5B8C;&#x6574;&#x4EE3;&#x7801;&#x5982;&#x4E0B;</p>
<pre class="language-"><code class="lang-JavaScript">/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    let n = word1.length;
    let  m = word2.length;
    if(n * m == 0){
        return n+m;
    }
    // &#x4E8C;&#x7EF4;&#x6570;&#x7EC4;
    var dp = Array.from(new Array(n+1),() =&gt; new Array(m+1).fill(0));
    for(let i = 1;i &lt;= n;++i){
        dp[i][0] = dp[i-1][0] + 1;
    }
    for(let j = 1;j &lt;= m;++j){
        dp[0][j] = dp[0][j-1] + 1;
    }
    for(let i = 1 ; i &lt;= n ; i ++){
        for(let j = 1 ; j &lt;= m ; j ++){
            if(word1[i-1] === word2[j-1]){
                dp[i][j] = dp[i-1][j-1]
            }else{
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
            }
        }
    }
    return dp[n][m]
};
</code></pre>
<p>&#x5176;&#x5B9E;&#x8FD9;&#x4E2A;&#x65B9;&#x6CD5;&#x53EF;&#x4EE5;&#x8FDB;&#x884C;&#x4F18;&#x5316;&#x7684; &#x56E0;&#x4E3A;&#x6211;&#x4EEC;&#x6709;&#x7684;&#x5B50;&#x4EFB;&#x52A1;&#x6709;&#x91CD;&#x590D;&#x8BA1;&#x7B97;</p>
<footer class="page-footer"><span class="copyright">Copyright &#xA9; YoungGary 2019 all right reserved&#xFF0C;powered by Gitbook</span><span class="footer-modification">&#x8BE5;&#x6587;&#x4EF6;&#x4FEE;&#x8BA2;&#x65F6;&#x95F4;&#xFF1A;
2021-09-09 22:08:17
</span></footer>
                                
                                </section>
                            
    </div>
    <div class="search-results">
        <div class="has-results">
            
            <h1 class="search-results-title"><span class='search-results-count'></span> results matching "<span class='search-query'></span>"</h1>
            <ul class="search-results-list"></ul>
            
        </div>
        <div class="no-results">
            
            <h1 class="search-results-title">No results matching "<span class='search-query'></span>"</h1>
            
        </div>
    </div>
</div>

                        </div>
                    </div>
                
            </div>

            
                
                <a href="322.html" class="navigation navigation-prev " aria-label="Previous page: 322.零钱兑换">
                    <i class="fa fa-angle-left"></i>
                </a>
                
                
                <a href="../flutter/" class="navigation navigation-next " aria-label="Next page: Flutter从入门到放弃">
                    <i class="fa fa-angle-right"></i>
                </a>
                
            
        
    </div>

    <script>
        var gitbook = gitbook || [];
        gitbook.push(function() {
            gitbook.page.hasChanged({"page":{"title":"72.编辑距离","level":"1.2.12","depth":2,"next":{"title":"Flutter从入门到放弃","level":"1.3","depth":1,"path":"flutter/README.md","ref":"flutter/README.md","articles":[{"title":"1.Dart语言(1)","level":"1.3.1","depth":2,"path":"flutter/dart1.md","ref":"flutter/dart1.md","articles":[]},{"title":"2.Dart语言(2)","level":"1.3.2","depth":2,"path":"flutter/dart2.md","ref":"flutter/dart2.md","articles":[]},{"title":"3.Flutter初始化","level":"1.3.3","depth":2,"path":"flutter/widget1.md","ref":"flutter/widget1.md","articles":[]},{"title":"4.Container和Text组件","level":"1.3.4","depth":2,"path":"flutter/containerText.md","ref":"flutter/containerText.md","articles":[]},{"title":"5.Image组件","level":"1.3.5","depth":2,"path":"flutter/image.md","ref":"flutter/image.md","articles":[]},{"title":"6.Flutter 技术总结","level":"1.3.6","depth":2,"path":"flutter/chapter2.md","ref":"flutter/chapter2.md","articles":[]}]},"previous":{"title":"322.零钱兑换","level":"1.2.11","depth":2,"path":"leetcode/322.md","ref":"leetcode/322.md","articles":[]},"dir":"ltr"},"config":{"plugins":["theme-comscore","prism","-highlight","copy-code-button","search-pro","-search","-lunr","expandable-chapters","splitter","-sharing","tbfed-pagefooter","anchor-navigation-ex"],"styles":{},"pluginsConfig":{"tbfed-pagefooter":{"copyright":"Copyright &copy YoungGary 2019","modify_label":"该文件修订时间：","modify_format":"YYYY-MM-DD HH:mm:ss"},"prism":{"css":["prismjs/themes/prism-solarizedlight.css"],"lang":{"shell":"bash"}},"splitter":{},"search-pro":{},"fontsettings":{"theme":"white","family":"sans","size":2},"anchor-navigation-ex":{"associatedWithSummary":true,"float":{"floatIcon":"fa fa-navicon","level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"mode":"float","multipleH1":true,"pageTop":{"level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"printLog":false,"showGoTop":true,"showLevel":false},"theme-comscore":{},"copy-code-button":{},"theme-default":{"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"showLevel":false},"expandable-chapters":{}},"theme":"default","author":"Gary","pdf":{"pageNumbers":true,"fontSize":12,"fontFamily":"Arial","paperSize":"a4","chapterMark":"pagebreak","pageBreaksBefore":"/","margin":{"right":62,"left":62,"top":56,"bottom":56}},"structure":{"langs":"LANGS.md","readme":"README.md","glossary":"GLOSSARY.md","summary":"SUMMARY.md"},"variables":{},"title":"Gary的小窝","language":"zh-hans","gitbook":"*","description":"Gary的小窝. 里面包含了个人撰写的技术文章"},"file":{"path":"leetcode/72.md","mtime":"2021-09-09T14:08:17.740Z","type":"markdown"},"gitbook":{"version":"3.2.3","time":"2021-09-09T14:10:10.930Z"},"basePath":"..","book":{"language":""}});
        });
    </script>
</div>

        
    <script src="../gitbook/gitbook.js"></script>
    <script src="../gitbook/theme.js"></script>
    
        
        <script src="../gitbook/gitbook-plugin-copy-code-button/toggle.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/jquery.mark.min.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/search.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-splitter/splitter.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-fontsettings/fontsettings.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-theme-comscore/test.js"></script>
        
    

    </body>
</html>

